package com.wenhao.leetcode.hard;

import java.util.Deque;
import java.util.LinkedList;

/**
 * 题目:https://leetcode-cn.com/problems/largest-rectangle-in-histogram/
 * 柱状图中最大的矩形
 *
 * 用到了单调栈 这一题需要定期复习
 *
 * @author Wenhao Tong
 * @Description
 * @create 2021-06-30 13:00
 */
public class LeetCode84 {
    public static void main(String[] args) {
        LeetCode84 leetCode84 = new LeetCode84();
        leetCode84.largestRectangleArea(new int[]{0,9});
    }

    public int largestRectangleArea(int[] heights) {
        Deque<Integer> stack = new LinkedList<>();
        int[] left = new int[heights.length];
        int[] right = new int[heights.length];
        for (int i = 0;i < heights.length;i++) {
            while (stack.size() > 0 && heights[i] <= heights[stack.peek()]) {
                stack.pop();
            }
            left[i] = stack.size() == 0 ? -1 : stack.peek();
            stack.push(i);
        }
        stack = new LinkedList<>();
        for (int i = heights.length - 1;i > - 1;i--) {
            while (stack.size() > 0 && heights[i] <= heights[stack.peek()]) {
                stack.pop();
            }
            right[i] = stack.size() == 0 ? heights.length : stack.peek();
            stack.push(i);
        }
        int max = 0;
        for (int i = 0;i < heights.length;i++) {
            int temp = heights[i] * (right[i] - left[i] - 1);
            max = max > temp ? max : temp;
        }
        return max;
    }
}
